public class WordSearch {

	static boolean patternMatch(char[][] arr, int m, int n, char[] pattern)
	{
		boolean[][] visited = new boolean[m][n];
		boolean found = false;

		//mark all as unvisited
		for(int i = 0 ; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				visited[i][j] = false;
			}
		}

		//see if pattern matches for every position

		for(int i = 0 ; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if( findPattern(arr,i,j,m,n,pattern,0,visited) == true )
				{
					found = true;
					break;
				}
			}
			if(found==true)
				break;
		}

		return found;
	}

	static int[] delta_i = {-1,-1,-1,0,1,1,1,0};
	static int[] delta_j = {1,0,-1,-1,-1,0,1,1};

	static boolean findPattern(char[][] arr, int i, int j, int m, int n, char[] pattern,int patternIndex,boolean[][] visited)
	{
		
		char[] p = pattern;

		//base cases
		if(pattern[patternIndex] == '\0')
			return true;

		if(i<0 || i >= m-1 || j<0 || j >= n-1)
			return false;

		if(arr[i][j] != pattern[patternIndex] || visited[i][j] == true)
			return false;

		visited[i][j] = true;
		
		for(int k = 0; k < 8; k++)
		{
			if(patternIndex+1 < pattern.length)
			if(findPattern(arr,i+delta_i[k],j+delta_j[k],m,n,pattern,patternIndex+1,visited)==true)
				return true;
		}
		
		
		
		return(visited[i][j] = false);
	}	

	public static void main(String[] args) {
		char[][] arr = {	{'A','C','P','R','C'},
							{'X','S','O','P','C'},
							{'V','O','V','N','I'},
							{'W','G','F','M','N'},
							{'Q','A','T','I','T'}}; 
		//char[] pattern = {'M','I','C','R','O','\0'};
		//char[] pattern = {'A','X','V','G','\0'};
		char[] pattern = {'F','V','O','\0'};
		System.out.println(patternMatch(arr,5,5,pattern));
	}
}